<?php
/**
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * PHP Version 5
 *
 * @category Go
 * @author   Wang Zhaogang <Wang Zhaogang@babamaiche.com>
 * @file     Go.php
 * @date     2016/9/6
 * @time     11:43
 * @license  http://chedamai.cn/ License
 * @link     http://chedamai.cn/
 */

namespace app\components;
/**
 * The Go class is used for ***
 *
 * @category Go
 * @author   Wang Zhaogang <Wang Zhaogang@babamaiche.com>
 * @class    Go
 * @date     2016/9/6
 * @time     11:43
 * @license  http://chedamai.cn/ License
 * @link     http://chedamai.cn/
 */

use yii;
use yii\log\Logger;
class Go
{
    public static $shapeLists;
    public static $currentList;
    public static $currentShapeId;
    public static $currentRevert;
    public static $currentRotate;
    public static $allShapes = [];
    public static $selectedShapes = [];
    public static $tried = [];
    /**
     * Go constructor.
     * @param array $allShapes
     */
    public static function initShapes()
    {
        $shapes = [];
        //1
        $shapes[] = new Shape(0, 5, 1, [
            [1,1,1,1,1],
        ], "#FF3366");
        //2
        $shapes[] = new Shape(1, 2, 4, [
            [0,1],
            [0,1],
            [0,1],
            [1,1],
        ], "#FF9900");
        //3
        $shapes[] = new Shape(2, 4, 2, [
            [1,1,1,1],
            [0,0,1,0],
        ], "#996600");
        //4
        $shapes[] = new Shape(3, 4, 2, [
            [1,1,0,0],
            [0,1,1,1],
        ], "#000000");
        //5
        $shapes[] = new Shape(4, 3, 3, [
            [1,0,0],
            [1,0,0],
            [1,1,1],
        ], "#000099");
        //6
        $shapes[] = new Shape(5, 3, 2, [
            [1,1,1],
            [1,1,0],
        ], "#00FFFF");
        //7
        $shapes[] = new Shape(6, 3, 2, [
            [1,0,1],
            [1,1,1],
        ], "#FFFF00");
        //8
        $shapes[] = new Shape(7, 3, 3, [
            [1,1,0],
            [0,1,0],
            [0,1,1],
        ], "#CCCC99");
        //9
        $shapes[] = new Shape(8, 3, 3, [
            [1,1,0],
            [0,1,1],
            [0,1,0],
        ], "#99CC66");
        //10
        $shapes[] = new Shape(9, 3, 3, [
            [0,1,0],
            [0,1,0],
            [1,1,1],
        ], "#00CC00");
        //11
        $shapes[] = new Shape(10, 3, 3, [
            [0,1,1],
            [1,1,0],
            [1,0,0],
        ], "#FF0066");
        //12
        $shapes[] = new Shape(11, 3, 3, [
            [0,1,0],
            [1,1,1],
            [0,1,0],
        ], "#FF3300");
        //$shapes[1]->setRevert(1);
        //$shapes[4]->setRevert(1);
        //$shapes[8]->setRevert(1);
        $shapes[3]->setRotate(1);
        self::$allShapes = $shapes;
    }
    private static function pc_next_permutation($p, $size) {
        // slide down the array looking for where we're smaller than the next guy
        for ($i = $size - 1;$i >= 0 && $p[$i] >= $p[$i+1]; --$i) { }

        // if this doesn't occur, we've finished our permutations
        // the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
        if ($i == -1) { return false; }

        // slide down the array looking for a bigger number than what we found before
        for ($j = $size; $j >=0 && $p[$j] <= $p[$i]; --$j) { }

        // swap them
        $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;

        // now reverse the elements in between by swapping the ends
        for (++$i, $j = $size; $i < $j; ++$i, --$j) {
            $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
        }

        return $p;
    }

    public static function generateShapeList($selectedShapes) {
        $size = count($selectedShapes) - 1;
        $perm = range(0, $size);
        $j = 0;
        $perms = [];
        do {
            foreach ($perm as $i) { $perms[$j][] = $selectedShapes[$i]; }
        } while ($perm = self::pc_next_permutation($perm, $size) and ++$j);
        self::$shapeLists = $perms;
    }
    public static function initParams() {
        self::$currentList = 0;
        self::$currentShapeId = 0;
        self::$currentRevert = 0;
        self::$currentRotate = 0;
        self::$tried = [];
    }
    public static function getNextShapeList() {
        if (self::$currentList >= count(self::$shapeLists)) {
            return false;
        }
        return self::$currentList++;
    }
    public static function getNextShapeId() {
        $currentShapeList = self::$shapeLists[self::$currentList];
        if (self::$currentShapeId >= count($currentShapeList)) {
            return false;
        }
        return self::$currentShapeId++;
    }
    public static function cancelShapeId() {
        self::$currentShapeId-=2;
        if (self::$currentShapeId < 0) {
            self::$currentShapeId = 0;
        }
    }
    public static function isLastShape() {
        $currentShapeList = self::$shapeLists[self::$currentList];
        return self::$currentShapeId === (count($currentShapeList) - 1);
    }
    public static function getNextRevert() {
        if (self::$currentRevert >= 2) {
            return false;
        }
        return self::$currentRevert++;
    }
    public static function getNextRotate() {
        if (self::$currentRotate >= 4) {
            return false;
        }
        return self::$currentRotate++;
    }
    public static function recordTriedPath($pathHash) {
        self::$tried[] = $pathHash;
    }
    public static function checkTriedPath($path, $newNode, $debug = false) {
        $tmpPath = [];
        foreach($path as $node) {
            $tmpPath[] =    $node;
        }
        array_push($tmpPath, $newNode);
        $check = false;
        foreach(self::$tried as $triedPathHash) {
            if (count($tmpPath) === count($triedPathHash)) {
                $count = count($tmpPath);
                $equal = true;
                for ($i = 0; $i < $count; $i++) {
                    $hash = Plate::nodeToHash($tmpPath[$i]);
                    if ($debug) {
                        //Yii::getLogger()->log('内部检查：' . print_r([
                        //        'hash' => $hash,
                        //        'node' => $tmpPath[$i],
                        //        'i' => $i,
                         //       'triedPathHash' => $triedPathHash[$i],
                         //   ], true), Logger::LEVEL_INFO);

                    }
                    if ($hash !== $triedPathHash[$i]) {
                        $equal = false;
                        break;
                    }
                }
                if ($equal) {
                    return true;
                }
            }
        }
        return $check;
    }
    public static function findPath($width, $selectedShapes) {
        //初始化底盘
        $plate = new Plate($width);
        //初始化参数
        self::initParams();
        //初始化形状序列
        self::generateShapeList($selectedShapes);
        //Yii::getLogger()->log('形状列表:' . print_r(self::$shapeLists, true), Logger::LEVEL_INFO);

        //尝试下一个形状序列
        $shapeListId = self::getNextShapeList();
        $shapeList = self::$shapeLists[$shapeListId];
        $shapeIndex = 0;
        $protect = 0;
        do {
            //尝试下一个形状
            $shapeId = self::getNextShapeId();
            //Yii::getLogger()->log('当前shapeId：' . self::$currentShapeId, Logger::LEVEL_INFO);
            if ($shapeId === false) {
                break;
            }
            $putSuccess = false;
            //获取形状
            $orgShape = self::$allShapes[$shapeList[$shapeId]];
            $shape = clone $orgShape;

            //找到空的格子
            $emptyPositions = $plate->getEmptyPositions();
            foreach($emptyPositions as $pos) {
                $x = $pos[0];
                $y = $pos[1];

                //尝试各种姿势
                $shape->clearPlacement();
                while ($shape->nextPlacement()) {
                    //看看是否走过
                    try {
                        $debug = false;
                        if (self::checkTriedPath($plate->getPath(), [$shape, $x, $y], $debug)) {
                            //Yii::getLogger()->log('此路已经走过。', Logger::LEVEL_INFO);
                            continue;
                        };
                    } catch (\Exception $e) {
                        //Yii::getLogger()->log(print_r([
                        //    self::$tried,
                        //    $plate->getPath(),
                        //    [$shape, $x, $y],
                        //    $e->getTraceAsString()
                        //], true), Logger::LEVEL_INFO);
                        return ['success' => false, 'message' => '异常。。'];
                    }
                    //尝试能否放下形状
                    if ($plate->putShape($shape, $x, $y)) {
                        //Yii::getLogger()->log('能放下。hash:' . Plate::nodeToHash([$shape, $x, $y]), Logger::LEVEL_INFO);
                        //Yii::getLogger()->log('形状:' . Shape::formatArray($shape->toArray()['data']), Logger::LEVEL_INFO);
                        //Yii::getLogger()->log('姿势:' . print_r($shape->getPlacement(), true), Logger::LEVEL_INFO);
                        //Yii::getLogger()->log('位置:' . print_r($pos, true), Logger::LEVEL_INFO);
                        //Yii::getLogger()->log('底盘：' . Shape::formatArray($plate->getData()), Logger::LEVEL_INFO);
                        //能放下，则看是否已经放满
                        if ($plate->getEmptyBlocks() <= 0) {

                            //底盘已满，形状是否用完
                            if ($shapeIndex >= count($shapeList) - 1) {
                                //Yii::getLogger()->log('全部放完，完成。', Logger::LEVEL_INFO);
                                //找到一条路径，完成
                                return ['success' => true, 'message' => '找到啦.', 'data' => $plate->getResult()];
                            } else {
                                //没有用完形状就拼满了底盘
                                //Yii::getLogger()->log('没有用完形状就拼满了底盘。' . $shapeIndex, Logger::LEVEL_INFO);
                                return ['success' => false, 'message' => '没有用完形状就拼满了底盘'. $shapeIndex];
                            }
                        } else {
                            //Yii::getLogger()->log('继续下一个形状', Logger::LEVEL_INFO);
                            $shapeIndex++;
                            //没有放满则继续一下个形状
                            $putSuccess = true;
                            break;
                        }
                    }
                }
                if ($putSuccess) {
                    break;
                }
            }
            //任何空格都放不下
            if (!$putSuccess) {
                //记录这个失败的尝试
                $pathHash = $plate->getPathHash();
                self::recordTriedPath($pathHash);
                //Yii::getLogger()->log('回退前底盘：' . Shape::formatArray($plate->getData()), Logger::LEVEL_INFO);
                //Yii::getLogger()->log('回退前Path：' . print_r($plate->getPath(), true), Logger::LEVEL_INFO);

                $node = $plate->popShape(true);
                self::cancelShapeId();
                //Yii::getLogger()->log('回退:' .print_r(
                //    [
                //        'shapeId' => $node[0]->getId(),
                //        'placement' => $node[0]->getPlacement(),
                //        'data' => Shape::formatArray($node[0]->toArray()['data']),
                //        'x' => $node[1],
                //        'y' => $node[2],
                //   ], true), Logger::LEVEL_INFO);
                //Yii::getLogger()->log('回退后底盘：' . Shape::formatArray($plate->getData()), Logger::LEVEL_INFO);
                //Yii::getLogger()->log('当前shapeId：' . self::$currentShapeId, Logger::LEVEL_INFO);
                //Yii::getLogger()->log('tried：' .  print_r(self::$tried, true), Logger::LEVEL_INFO);

            }
            //break;
        } while ($protect++ < 20000);
        return ['success' => false, 'message' => '用完形状也找不到.', 'data' => $plate->getResult()];
    }

}